//
// Created by REEJI2219 on 2024-09-13.
//
#include <iostream>
using namespace std;
class ParentTreeNode {
public:
    char data;
    int pIndex;
};
class LinkBinaryTreeNode {
public:
    char data;
    //子节点
    LinkBinaryTreeNode *child;
    //兄弟节点
    LinkBinaryTreeNode *brother;
    void prePrint() {
        printf("%c ",data);
        if(child!=nullptr) {
            child->prePrint();
        }
        if(brother!=nullptr) {
            brother->prePrint();
        }
    }
    void centerPrint() {
        if(child!=nullptr) {
            child->centerPrint();
        }
        printf("%c ",data);
        if(brother!=nullptr) {
            brother->centerPrint();
        }
    }
};
class  ParentTree {
private:
    ParentTreeNode *list;
    int max;
    int last;
public:
    ParentTree() {
        max = 30;
        last = 0;
        list = new ParentTreeNode[max];
    }
    void addData(char data,int pIndex) {
        ParentTreeNode *tree_node =new ParentTreeNode();
        tree_node->data=data;
        tree_node->pIndex = pIndex;
        list[last]=*tree_node;
        last++;
    }
    void printTree() {
        for(int i=0;i<last;i++) {
            printf("%c, %d \n",list[i].data,list[i].pIndex);
        }
    }
};

class LinkTreeNode {
public:
    char data;
    int *childList;
    int last ;
    LinkTreeNode() {
        last=0;
        childList = new int[5];
        for(int i=0;i<5;i++) {
            childList[i]=-2;
        }
    }
    void addChild(int childIndex) {
        if(last==5) {
            return;
        }
        childList[last]= childIndex;
        last++;
    }
};
class LinkTree {
private:
    LinkTreeNode *list;
    int max;
    int last;
public:
    LinkTree() {
        max=20;
        last = 0;
        list = new LinkTreeNode[max];
    }
    void add(LinkTreeNode *tree_node) {
        list[last] = *tree_node;
        last++;
    }
    void printTree() {
        for(int i=0;i<last;i++) {
            printf("%d %c, ",i,list[i].data);
            for(int j=0;j<5;j++) {
                int childIndex = list[i].childList[j];
                if(childIndex!=-2) {
                    printf("%d ",childIndex);
                }else {
                    break;
                }
            }
            printf("\n");
        }
    }
    LinkBinaryTreeNode *transToBinaryTree() {
        return transToBinaryTree(list[0]);
    }
    LinkBinaryTreeNode *transToBinaryTree(LinkTreeNode tree_node) {
        LinkBinaryTreeNode *bNode = new LinkBinaryTreeNode();
        bNode->data =tree_node.data;
        LinkBinaryTreeNode *preTree=nullptr;
        for(int i=0;i<5;i++) {
            int childIndex = tree_node.childList[i];
            //-2说明没有子节点了，直接跳出
            if(childIndex==-2) {
                break;
            }
            //前置不存在，则创建
            if(preTree==nullptr) {
                preTree = transToBinaryTree(list[childIndex]);
                //第一个前置为左孩子
                bNode->child = preTree;
            }else {
                //其他为右孩子
                preTree->brother = transToBinaryTree(list[childIndex]);
                preTree = preTree->brother;
            }
        }
        return bNode;
    }
};


// int main(int argc, char *argv[]) {
//     // ParentTree *parent_tree = new ParentTree();
//     // parent_tree->addData('A',-1);
//     // parent_tree->addData('B',0);
//     // parent_tree->addData('C',0);
//     // parent_tree->addData('D',1);
//     // parent_tree->addData('E',1);
//     // parent_tree->addData('F',2);
//     // parent_tree->addData('G',3);
//     // parent_tree->printTree();
//     LinkTree *linkTree = new LinkTree();
//     LinkTreeNode *treeNode = new LinkTreeNode();
//     treeNode->data ='A';
//     treeNode->addChild(1);
//     treeNode->addChild(2);
//     treeNode->addChild(6);
//     linkTree->add(treeNode);
//     LinkTreeNode *treeNode1 = new LinkTreeNode();
//     treeNode1->data ='B';
//     treeNode1->addChild(3);
//     treeNode1->addChild(4);
//     linkTree->add(treeNode1);
//     LinkTreeNode *treeNode2 = new LinkTreeNode();
//     treeNode2->data ='C';
//     treeNode2->addChild(5);
//     linkTree->add(treeNode2);
//     LinkTreeNode *treeNode3 = new LinkTreeNode();
//     treeNode3->data ='D';
//     linkTree->add(treeNode3);
//     LinkTreeNode *treeNode4 = new LinkTreeNode();
//     treeNode4->data ='E';
//     linkTree->add(treeNode4);
//     LinkTreeNode *treeNode5 = new LinkTreeNode();
//     treeNode5->data ='F';
//     linkTree->add(treeNode5);
//     LinkTreeNode *treeNode6 = new LinkTreeNode();
//     treeNode6->data ='G';
//     linkTree->add(treeNode6);
//     linkTree->printTree();
//     LinkBinaryTreeNode *binary_tree_node = linkTree->transToBinaryTree();
//     binary_tree_node->prePrint();
//     printf("\n");
//     binary_tree_node->centerPrint();
// }
